TNotes.leetcode

Appearance

0500. 键盘行【简单】

0500. 键盘行【简单】 ​

1. 📝 题目描述 ​

给你一个字符串数组 words，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

请注意，字符串 不区分大小写，相同字母的大小写形式都被视为在同一行。

美式键盘 中：

  • 第一行由字符 "qwertyuiop" 组成。
  • 第二行由字符 "asdfghjkl" 组成。
  • 第三行由字符 "zxcvbnm" 组成。

American keyboard

示例 1：

txt
输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]
解释：由于不区分大小写，"a" 和 "A" 都在美式键盘的第二行。

示例 2：

txt
输入：words = ["omk"]
输出：[]

示例 3：

txt
输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]

提示：

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • words[i] 由英文字母（小写和大写字母）组成

2. 🎯 s.1 - 暴力解法 ​

js
/**
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (words) {
  // 定义键盘三行的字母（包含大小写）
  const row1 = new Set('qwertyuiopQWERTYUIOP')
  const row2 = new Set('asdfghjklASDFGHJKL')
  const row3 = new Set('zxcvbnmZXCVBNM')

  // 判断字符属于哪一行
  const getRow = (char) => {
    if (row1.has(char)) return 1
    if (row2.has(char)) return 2
    if (row3.has(char)) return 3
    return 0
  }

  const result = []

  // 遍历每个单词
  for (const word of words) {
    if (word.length === 0) {
      result.push(word)
      continue
    }

    // 获取第一个字符所在的行
    const firstRow = getRow(word[0])
    let isCommonRow = true

    // 检查单词中所有字符是否都在同一行
    for (let i = 1; i < word.length; i++) {
      if (getRow(word[i]) !== firstRow) {
        isCommonRow = false
        break
      }
    }

    // 如果都在同一行，则加入结果
    if (isCommonRow) {
      result.push(word)
    }
  }

  return result
}
  • 时间复杂度：O(n×m)，其中 n 是单词数，m 是单词平均长度，每个字符都要检查行号。
  • 空间复杂度：O(1)，只用了固定的集合和变量，额外空间与输入无关。

3. 🎯 s.2 - 使用内置库 ​

js
/**
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (words) {
  // 定义键盘三行
  const rows = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']

  return words.filter((word) => {
    // 转为小写进行比较
    const lowerWord = word.toLowerCase()

    // 检查是否所有字符都在某一行中
    return rows.some((row) => {
      return lowerWord.split('').every((char) => row.includes(char))
    })
  })
}
  • 时间复杂度：O(n×m×r)，其中 r=3（行数固定），因为对每个单词要遍历行并逐字符检查，但 r 是常数，整体仍为 O(n×m)。
  • 空间复杂度：O(m)，因为 split 会生成临时数组，平均长度为 m。

4. 🎯 s.3 - 使用正则 ​

js
/**
 * @param {string[]} words
 * @return {string[]}
 */
var findWords = function (words) {
  return words.filter((word) =>
    /^([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)$/i.test(word)
  )
}
  • 时间复杂度：O(n×m)，每个单词都要逐字符匹配正则表达式。
  • 空间复杂度：O(1)，只用了常量大小的正则对象和结果数组，没有额外依赖于输入大小的空间。

Discussions